package org.geekbang.time.mathbasicthought.lesson10_depth_first_traversal;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

public class DFSTest {
    public static final TreeNode root = new TreeNode('根', "", null);

    public static void main(String[] args) {
        String[] words = {"hello", "world", "their", "name", "is", "baga"};

        for (String word : words) {
            insert(word);
        }

        /*System.out.println("their result:" + search("their"));
        System.out.println("a result:" + search("a"));
        System.out.println("name result:" + search("name"));*/

        //DFSAll(root);

        DFSAllByStack();
    }

    /**
     * 递归DFS树中的全部节点
     */
    private static void DFSAll(TreeNode curNode) {
        if (curNode == null)
            return;

        System.out.println("Current node :" + curNode);
        for (Map.Entry<Character, TreeNode> characterTreeNodeEntry : curNode.children.entrySet()) {
            DFSAll(characterTreeNodeEntry.getValue());
        }
    }

    /**
     * 利用栈进行DFS
     */
    private static void DFSAllByStack() {
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);

        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();

            // 到达叶子节点
            if (node.children.size() == 0) {
                System.out.println(node);
            } else {

                // 使用一个临时栈变量，保证DFS子节点的顺序，如果不在意顺序，可以不用这个stack倒序，当然也可以用其他方法保证顺序
                Stack<TreeNode> stackTemp = new Stack<>();
                for (Map.Entry<Character, TreeNode> characterTreeNodeEntry : node.children.entrySet()) {
                    stackTemp.push(characterTreeNodeEntry.getValue());
                }

                while (!stackTemp.isEmpty()) {
                    stack.push(stackTemp.pop());
                }
            }
        }
    }

    public static void insert(String word) {
        if (word == null || word.trim().length() == 0)
            return;

        TreeNode newNode = root;
        char[] chars = word.toCharArray();
        StringBuilder prefix = new StringBuilder();

        for (int i = 0; i < chars.length; i++) {
            char letter = chars[i];
            prefix.append(letter);

            TreeNode treeNode = newNode.children.get(letter);
            if (treeNode == null) {
                treeNode = new TreeNode(letter, prefix.toString().substring(0, prefix.length() - 1), null);
                newNode.children.put(letter, treeNode);
            }

            newNode = treeNode;
        }

        switch (word) {
            case "hello":
                newNode.explanation = "你好";
                break;
            case "name":
                newNode.explanation = "名字";
                break;
            default:
                newNode.explanation = "其他";
        }
    }

    /**
     * DFS树中等于word的路径
     *
     * @param word
     * @return
     */
    public static TreeNode search(String word) {
        if (word == null || word.trim().length() == 0)
            return null;

        TreeNode searchNode = root;
        char[] chars = word.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            char letter = chars[i];

            searchNode = searchNode.children.get(letter);

            if (searchNode == null)
                break;
        }

        if (searchNode != null && searchNode.explanation != null) {
            return searchNode;
        }

        return null;
    }

    static class TreeNode {
        public char label;
        public HashMap<Character, TreeNode> children = null;
        public String prefix = null;
        public String explanation = null;

        public TreeNode(char label, String prefix, String explanation) {
            this.label = label;
            this.children = new HashMap<>();
            this.prefix = prefix;
            this.explanation = explanation;
        }

        @Override
        public String toString() {
            return "TreeNode{" +
                    "label=" + label +
                    ", prefix='" + prefix + '\'' +
                    ", explanation='" + explanation + '\'' +
                    '}';
        }
    }
}
